Gramáticas Equivalentes

Dos gramáticas G ₁ y G ₂ son equivalentes

G ₁ ≡ G ₂

si y solo si:

L(G ₁) = L(G ₂)

es decir, si ambas gramáticas generan el mismo lenguaje.

Recursión Izquierda

Uno de los problemas que encontramos al escribir un analizador sintáctico descendente son las producciones cuyos lados derechos comienzan por el mismo símbolo en el lado izquierdo:

A → Aα
A → β

ya que un analizador descendente basado en dicha gramática puede tomar la decisión de substituir el lado izquierdo por el lado derecho recursivo infinitamente.

Una gramática es recursiva izquierda si existe un no-terminal A tal que existen derivaciones: S ⇒+ A y A ⇒+ Aδ

Afortunadamente disponemos de un algoritmo para transformar gramáticas con recursión izquierda en gramáticas equivalentes sin dicha recursión.

Eliminación de la Recursión Izquierda

Las producciones de la forma:

A → Aα₁ | ... | Aα_m | β₁ | ... | β_n

donde los β_i son los lados derechos que no son recursivos por la izquierda, se transofrman en:

A → β₁ A' | ... | β_n A'
A' → α₁ A' | ... | α_m A' | ε

Ejemplo

En notación ANTLR:

instr : "{" bloque "}" ;
instr : "x";
bloque : lista_instr | ;
lista_instr : lista_instr ";" instr | instr;

Eliminamos la recursión izquierda así:

lista_instr : instr lista_instr2;
lista_instr2 : ";" instr lista_instr2 | ;

También, dado que ANTLR es una notación estilo BNF, podemos intiutivamente escribir:

lista_instr : instr (";" instr)*;

Ejemplo del Libro del Dragón

E → E + T|T
T → T * F|F
F →( E ) | id

que es recursiva izquierda, se transforma en:

E → TE'
E'→ +TE' | ε
F →( E ) | id

Eliminación Total de la Recursión

1. Ordenar los no-terminales asignándoles un número: A1...An
2. for(int i= 1; i <= n; i++)
   1. for(int j = 1; j < i; j++)
      • foreach(A _i → A _jα && A _j → β₁ | ... | β_n)
        • definir A _i → β₁α |... | β_nα
   2. eliminar la recursión directa por la izquierda de A _i

Ejemplo

La siguiente gramática exhibe recursión izquierda indirecta:

Σ={a,b}
N={S,A,B}

1. S → Ab
2. S → Ba
3. S → ε
4. A → Sa
5. A → a
6. B → Sb
7. B → b

Esto puede observarse al intentar hacer un Analisis Sintactico Descendente recursivo:

S ⇒₁ Ab ⇒₄ Sab ⇒₁ Abab ⇒₄ Sabab ⇒₁ Ababab ...

En este caso, S ⇒^* Sβ (a partir de S se deriva una Forma Sentencial que comienza por el mismo no-terminal), lo cual indica que hay recursión izquierda (que es posible aplicar una misma serie de sustituciones de lados izquierdos por lados derechos indefinidamente).

Los pasos para eliminar la recursión izquierda en la Gramatica dada son los siguientes:

1. Eliminación de la recursión directa en S.

   S → Ab
   S → Ba
   S → ε
   A → Sa
   A → a
   B → Sb
   B → b

2. Sustitución de prefijos S en el lado derecho de producciones con lado izquierdo A

   S → Ab
   S → Ba
   S → ε
   A → Aba
   A → Baa
   A → a

   1. B → Sb
   2. B → b

3. Eliminación de la recursión izquierda directa en producciones con lado derecho A

   S → Ab
   S → Ba
   S → ε
   A → BaaA'
   A → aA'
   A'→ baA'
   A'→ ε
   B → Sb
   B → b

4. Sustitución de prefijos S en el lado derecho de producciones con lado izquierdo B

   S → Ab
   S → Ba
   S → ε
   A → BaaA'
   A → aA'
   A'→ baA'
   A'→ ε
   B → Abb
   B → Bab
   B → b

5. Sustitución de prefijos A en lados derechos de producciones con lados izquierdos B

   S → Ab
   S → Ba
   S → ε
   A → BaaA'
   A → aA'
   A'→ baA'
   A'→ ε
   B → BaaA'bb
   B → aA'bb
   B → Bab
   B → b

6. Eliminación de la recursión izquierda directa en producciones con lado derecho B

   S → Ab
   S → Ba
   S → ε
   A → BaaA'
   A → aA'
   A'→ baA'
   A'→ ε
   B → aA'bbB'
   B → bB'
   B' → aaA'bbB'
   B' → abB'
   B' → B
   B'→ ε

Otra solución

Una mejor solución se puede lograr dándose cuenta que la gramática con recursión izquierda indirecta es una Gramatica Regular. En particular, es una gramática lineal derecha, la cual tiene una gramática lineal izquierda equivalente que no es recursiva izquierda:

1. S → bA
2. S → aB
3. S → ε
4. A → aS
5. A → a
6. B → bS
7. B → b

Ejemplo

A veces, podemos eliminar la recursión izquierda usando otros mecanismos.

Por ejemplo, cuando eliminamos la ambigüedad de la siguiente gramática, también eliminamos la recursión izquierda.

E → E + E
E → E - E
E → E * E
E → E / E
E → ( E )
E → id
E → num

E → T + E | T - E | T
T → F * T | F / T | F
F → ( E ) | id | num

Usando la notación BNF de ANTLR, la gramática puede escribirse de esta forma:

e : t (("+"|"-") t)*;
t : f (("*"|"/") f)*;
f : "(" e ")" | ID | NUM;

Factorización Izquierda

Una manera en la que podemos hacer la simulación de un analizador sintáctico descendente más eficiente, es eliminando los prefijos comunes en los lados derechos de las producciones.

Dada una gramática con producciones:

A → αβ₁ | ... | αβ_n | δ₁ | ... | δ_m

donde α es el prefijo común, y los δ_i son las producciones que no comparten el prefijo en cuestión, podemos factorizar los prefijos comunes en las producciones así:

A → α (β₁ | ... | β_n) | δ₁ | ... | δ_m

Y transformar la gramática en:

A → αA' | δ₁ | ... | δ_m
A'→ β₁ | ... | β_n

Al eliminar los prefijos comunes ya no es necesario que las implementaciones de los lados derechos consuman varias veces el mismo prefijo en la búsqueda del lado derecho correcto.